Global positioning systems and mobile phone networks are making it possible to track individual users with an increasing accuracy. One attractive application of knowing the geographic location of users is to compute and maintain social networks. In these networks, each user specifies a group of other users, called the user's friends. Whenever a friend moves into the user's vicinity, both users are notified by an alert message. In a more general context, a social group is one that is predefined by enrollment or by matching the personal profiles of users. A group may refer to a list of individuals but also to other groups of individuals.
The problem of maintaining social networks is a form of a dynamic query into a database of multiple geographic entities. In some applications, this could as well be part of a “find” query, coupled with other properties, such as profession, employer, user profile or calendar scheduling constraint. A natural example is of a traveling businessman who attends a large conference and would like to be alerted of and possibly meet other colleagues if they happened to be around. Other examples could be a roadside service, where service cars need to be dynamically assigned to new customers, or a surveillance system tracking suspects and directing security people.
Two different computational frameworks could be used in creating a social network. In the centralized computation model, users send their location information to a centralized server that keeps track of user locations and lists of friends and is responsible for computing and sending the alert messages to all pairs of friends. The peer-to-peer computation model involves no central server. Instead, each pair of friends is responsible for keeping each other informed about their location, detecting vicinity events, and transmitting alert messages.
Under both frameworks there is need for communication resources as well as computational resources. Communication is required to deliver location updates and alerts. The amount of communication is characterized by the number of messages being replaced, assuming that all the messages are of fixed length (i.e., location update of k users, for example, would require O(k) messages). Communication complexity affects the required amount of air time. In a simple cost model, a message between two users could be assumed to cost the same as a message between a user to a centralized server. More elaborate cost modes may be applied.
In addition, computational resources are needed, either on the server or on the participating moving devices, to keep and maintain data structures and to detect meeting alerts. Minimization of air time is critical as air time is typically the more expensive component of the two in building a real system. However, this relationship may depend on other considerations.
There are several considerations that impact both computational and communication complexities. A major consideration is the maximal velocity of users and the desired time/distance accuracy of alerts. For example, two users wish to receive an alert when the distance between them becomes shorter than R. An exact alert can not be provided, as this would require an infinitely large number of location updates and distance computations to find the exact moment that the distance between the two users becomes R. To overcome this problem in defining the desired event, a distance tolerance is introduced into the task. An alert needs to be sent before the two users arrive at a distance R between them, but not earlier than a distance of R+ε.
This model allows computation of the number of messages required to achieve any desired alert accuracy. It is further assumed that messages are transferred with no delay. This is analogous to the assumption v*tdelay<ε, for v representing the velocity. Consequently, a distance tolerance at the time of receiving the alert, R−ε, can naturally incorporate such practically small delays. The system and method provided hereby are general and do not depend on a specific definition of the task.
The choice of algorithm for maintaining social networks is an important issue. The number of messages would depend not only on the number of users, n, the distances between them, the vicinity radius R and the desired tolerance ε, but also on the nature of their motion trajectories and relations between them. In the computational geometry literature, the kinetic model is a common paradigm for evaluating the efficiency of algorithms for maintaining dynamic structures.
In this paradigm, the role of the evaluated algorithm is to maintain some geometric properties for set of moving elements, where each element moves along a low-degree algebraic curve. From time to time, an event occurs, in which new elements are inserted, and existing elements are deleted or change their trajectories. The number of changes in the data structure is evaluated as a function of the number of events in the dynamic input data set.
Algorithms for tracking moving objects are found in mobile computing literature, both in the database community, and in the mobile communications community. Much of the work assumes that moving objects are represented by simple point objects whose locations are continuously updated in an index. These moving objects, however, require continuous updating of the locations of all users, resulting in huge numbers of location update messages. Trajectory-based solutions are becoming increasingly popular.
Storing and indexing trajectories facilitates not only efficient spatial range queries but time-and-space range queries. Time-parameterized bounding rectangles and extends trajectory information with expiration information have also been addressed.
The problem of computing and maintaining mobile social networks is also related to the problem of finding people whose personal profiles match. For this problem, commercial solutions have been offered. However, the problems addressed in involving networks of mobile friends, present new challenges that have not been addressed before. Due to the enormous number of existing mobile phone users worldwide, it would require a huge number of messages to be replaced for repeatedly checking the location of each pair of friends in such a large population, which process would also be quite inefficient. Adequate algorithms are required to address these new problems.
What is needed is a system and an associated method for minimizing the number of location update messages between pairs of friends in addition to an efficient method for computation and data collection. The need for such system and method has heretofore remained unsatisfied.